package tree.tree2.symmetry.BinarySearchTree;

import tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName IsValidBST
 * @Description TODO
 * @Author lenovo
 * @Date 2023-05-05 10:34
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class IsValidBST {
    /**
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 有效 二叉搜索树定义如下：
     * <p>
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *  
     * 示例 1：
     * <p>
     * 输入：root = [2,1,3]
     * 输出：true
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode poll = queue.poll();

                if ((poll.left != null && poll.left.val > poll.val) || (poll.right != null && poll.right.val < poll.val)) {
                    return false;
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(3);
        IsValidBST isValidBST = new IsValidBST();
        System.out.println(isValidBST.isValidBST(treeNode));
    }
}